//
// Created by user on 2022/2/15.
//
#include<vector>
using namespace std;

int mergeAndCountReversePairs(vector<int> &nums, int lo, int mid, int hi, vector<int> &tmp);
int mergeSort(vector<int> &nums, int lo,  int hi, vector<int> &tmp);
int reversePairs(vector<int>& nums) {
    vector<int> tmp(nums.size(), 0);
    int count = mergeSort(nums, 0, nums.size()-1, tmp);
    return count;
}

int mergeSort(vector<int> &nums, int lo,  int hi, vector<int> &tmp){
    if(lo>=hi){return 0;}
    int mid = lo+(hi-lo)/2;
    int leftCount = mergeSort(nums, lo, mid, tmp);
    int rightCount = mergeSort(nums, mid+1, hi, tmp);

    int mergeCount = mergeAndCountReversePairs(nums, lo, mid, hi, tmp);
    return leftCount+rightCount+mergeCount;
}



int mergeAndCountReversePairs(vector<int> &nums, int lo, int mid, int hi, vector<int> &tmp){
    for (int i = lo; i <=hi ; ++i) {
        tmp[i] = nums[i];
    }

    int count =0;

    int i=lo;
    int j=mid+1;

    for (int k = lo; k <=hi; ++k) {
        if(i==mid+1){nums[k]=tmp[j++];}
        else if(j==hi+1){nums[k]=tmp[i++];}
        else if (tmp[i]<=tmp[j]){nums[k]=tmp[i++];}
        else{
            nums[k]=nums[j++];
            count += (mid - i + 1); //重点，计算个数
        }
    }
    return count;
}
int main(){

    return 0;
}